home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13107 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: airdmhor.gen.nz!not-for-mail
  2. From: gumboot@airdmhor.gen.nz (Simon Hosie)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: merge sort
  5. Date: 5 Apr 1996 04:57:53 +1200
  6. Organization: Airdmhor : a couple of BBS's, a bunch of people, and a cat.
  7. Message-ID: <4k0v2h$u3d@airdmhor.gen.nz>
  8. References: <315F6D06.79A7@cs.utas.edu.au>
  9. NNTP-Posting-Host: airdmhor.gen.nz
  10. X-Newsreader: TIN [version 1.2 PL2]
  11.  
  12. PC Lab User:
  13. > has anyone got some source for the "merge" algorithm used in mergesort?
  14.  
  15.   No, but I can make some up on the spot (as I usually do)..
  16.  
  17. int     Arr1[NUM_OF_FISH] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9 },
  18.     Arr2[NUM_OF_FISH],
  19.        *ArrPtrA = Arr1,
  20.        *ArrPtrB = Arr2,
  21.        *Ptr1,
  22.        *Ptr1End,
  23.        *Ptr2,
  24.        *Ptr2End,
  25.        *Dest,
  26.        *DestEnd;
  27.  
  28. int    ListSize,
  29.     i;
  30.  
  31. for (ListSize = 1; ListSize < NUM_OF_FISH; ListSize <<= 1)
  32. {
  33.     Dest = ArrPtrB;
  34.     for (i = 0; i < NUM_OF_FISH; i += ListSize + ListSize)
  35.     {
  36.     Ptr1 = ArrPtrA + i;
  37.         Ptr2 = ArrPtrA + i + ListSize;
  38.     Ptr1End = min(ArrPtrA + NUM_OF_FISH, Ptr1 + ListSize);
  39.     Ptr2End = min(ArrPtrA + NUM_OF_FISH, Ptr2 + ListSize);
  40.     DestEnd = min(ArrPtrB + NUM_OF_FISH, Arr2 + i + ListSize + ListSize);
  41.  
  42.         while (Dest < DestEnd && Ptr1 < Ptr1End && Ptr2 < Ptr2End)
  43.         *Dest++ = *Ptr1 < *Ptr2 ? *Ptr1++ : *Ptr2++;
  44.     while (Ptr1 < Ptr1End)
  45.         *Dest++ = *Ptr1++;
  46.     while (Ptr2 < Ptr2End)
  47.         *Dest++ = *Ptr2++;
  48.     }
  49.     Dest = ArrPtrA;
  50.     ArrPtrA = ArrPtrB;
  51.     ArrPtrB = Dest;
  52. }
  53.  
  54.   Is that what you want?  I'm not sure that I need the DestEnd check at all,
  55. but I can't be bothered thinking about whether it'll work without.
  56.